package 题目集.动态规划.最长递增子序列;

import java.util.Scanner;

/**
 * https://leetcode.cn/problems/longest-increasing-subsequence/description/
 * 还可以用线段树解
 */
public class ch05_最长递增子序列 {
    /**
     * dp[i]：以每个位置结尾的最长递增子序列的长度
     * 朴素递推
     */
    public int lengthOfLIS1(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int res = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            //找到之前所有比自己小的子序列，取最大值
            for (int j = 0; j < i; j++) {
                //如果nums[i]>nums[j]，那么dp[i]=dp[j]+1
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    /**
     * 解法2：贪心+二分
     * 如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
     * 在方法1中，dp[i]依赖的，所有以a[i]结尾的上升子序列集合中的所有倒数第二个元素，选择这些集合中长度最大的一个。
     * 我们维护一个数组 d[i]，d[i]表示长度为 i 的最长上升子序列的末尾元素的最小值。
     * 上面两句有些不好理解，简单讲的话。
     *      就是dp[i]之前的最长递增子序列长度为len，我们维护一个数组，这个数组保存着i位置之前的，len个递增的序列。
     *      因为要让上升满足尽可能小，所以找到之前第一个比自己大的位置，然后替换掉，方便后面的位置插入。而自己的长度就是这个位置+1。
     *      而查找比自己大的过程，可以用二分加速
     */
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] d = new int[n];
        int res = 1;
        d[0]=nums[0];
        for (int i = 1; i < n; i++) {
            int index = findMax(nums[i], 0, res, d);    //找到第一个比nums[i]大的位置
            d[index] = nums[i];
            res = Math.max(res, index + 1);
        }
        return res;
    }
    //找到第一个比n大的位置，如果没有，返回末尾的下一个位置
    public static int findMax(int n,int l,int r,int[] d){
        while (l<r){
            int mid=l+(r-l)/2;
            if (d[mid]<n){
                l=mid+1;
            }else {
                r=mid;
            }
        }
        return l;
    }

}
